#include <cstdio>
#include <cstring>

const int N = 1000005;
int n, m;
int r[N], d[N], s[N], t[N], val[N];

inline bool check(int x) {
  memset(val, 0, sizeof(val));
  for (int i = 1; i <= x; ++i) val[s[i]] += d[i], val[t[i] + 1] -= d[i];
  for (int i = 1; i <= n; ++i) {
    val[i] += val[i - 1];
    if (val[i] > r[i]) return false;
  }
  return true;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("P1083 借教室.in", "r", stdin);
  freopen("P1083 借教室.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &r[i]);
  for (int i = 1; i <= m; ++i) scanf("%d%d%d", &d[i], &s[i], &t[i]);
  int L = 0, R = n, mid;
  while (L <= R) {
    mid = (L + R) >> 1;
    if (check(mid))
      L = mid + 1;
    else
      R = mid - 1;
  }
  if (L - 1 == n)
    printf("0");
  else
    printf("-1\n%i", L);
  return 0;
}